package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.Node;

public class _029_剑指OfferII排序的循环链表 {

    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        }
        Node minNode = head;
        Node maxNode = head;
        Node temp = head.next;
        while (temp != head) {
            if (temp.val < minNode.val) minNode = temp;
            if (temp.val > maxNode.val) maxNode = temp;
            temp = temp.next;
        }

        if (minNode == maxNode) {
            // 插入到头结点后面
            maxNode.next = new Node(insertVal, maxNode.next);
        } else if (insertVal >= maxNode.val || insertVal <= minNode.val) {
            while (maxNode.next.val == maxNode.val) maxNode = maxNode.next;
            maxNode.next = new Node(insertVal, maxNode.next);
        } else {
            while (minNode.next.val < insertVal) minNode = minNode.next;
            minNode.next = new Node(insertVal, minNode.next);
        }
        return head;
    }


}
